//二分查找
class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
       
        int n = strs.size();
        if(n==0) return "";
        if(n==1) return strs[0]; 
        int minLength = INT_MAX;
        for(int i=0;i<n;++i){
            int curL=strs[i].size();
            minLength = min(minLength,curL);
        }
        int low = 0;
        int high = minLength-1;
        int ans = -1;
        while(low<=high){
            int mid = (low+high)/2;
            //判断mid是否符合二分算法
            string strF = strs[0];
            bool stop = false;
            int pre = -1;
            for(int i=0;i<n;++i){
                string temp = strs[i]; 
                for(int j=0;j<=mid;++j){
                    if(temp[j]!=strF[j]){
                        stop = true;
                        //mid遍历的最长前缀
                        pre = j-1;
                        break;
                    }
                    if(stop){break;}
                }
            }
            if(!stop){
                //相同则扫描右侧区间寻找更长的答案（mid此时符合前缀相同，记录答案）
                ans = mid;
                low = mid+1;
            }else{
                //左侧mid遍历已经找到了最短的相同队列，此时直接返回结果
                if(pre != -1){
                    ans = pre;
                    break;
                }
                //不同则去掉一个元素（最长是最后一个元素不同）
                high = mid-1;
            }
        }

        return strs[0].substr(0,ans+1);
    }
};